n=2000;
bracket=["(",")","(","(","(",")","(",")","(","(","(","(",")","(","(",")","(",")",")",")","(",")","(",")","(","(","(","(",")",")",")","(","(","(",")",")",")","(",")","(",")","(",")","(","(","(","(",")","(",")","(","(",")",")","(","(","(",")","(","(","(","(",")",")","(","(",")","(",")",")",")","(",")",")",")","(","(","(","(","(","(",")",")","(",")","(","(",")","(",")","(",")","(",")",")",")","(",")","(","(","(","(",")","(","(",")",")","(",")","(",")","(",")",")","(",")","(",")",")",")",")",")","(","(",")","(",")","(",")","(",")","(","(","(",")",")","(",")","(","(","(","(","(","(","(",")",")",")",")",")","(",")",")",")","(",")","(","(","(","(","(",")",")",")","(",")",")",")",")",")",")",")","(","(","(","(","(","(","(","(",")",")","(",")",")",")","(",")",")",")","(","(",")",")","(","(",")","(",")","(","(",")","(","(","(",")",")",")",")","(","(",")",")",")",")",")",")","(",")",")",")",")","(",")",")",")",")",")",")",")","(","(",")",")",")","(","(",")","(","(",")",")","(",")",")","(",")",")","(","(","(","(","(",")","(","(","(","(","(","(","(","(",")","(","(","(",")",")","(","(","(","(","(",")","(","(",")",")",")","(","(","(",")",")","(","(","(",")","(",")","(",")","(",")",")","(","(",")","(",")",")","(",")","(","(","(","(","(","(","(",")",")",")",")",")","(",")","(",")","(",")","(","(","(","(","(",")",")",")",")","(",")","(","(","(",")",")",")",")",")","(",")",")","(","(","(","(","(",")","(",")",")",")","(",")",")","(",")",")","(",")","(","(","(",")",")",")","(","(",")","(",")",")","(",")","(",")","(",")","(",")",")","(",")",")","(",")","(",")","(",")",")",")","(",")","(","(",")",")",")",")","(","(",")",")","(",")","(",")",")",")",")","(","(",")","(","(","(",")","(",")",")","(",")","(","(","(",")","(","(","(","(",")",")",")","(","(",")",")","(",")",")","(","(","(","(",")",")",")",")","(",")",")","(","(","(",")",")",")",")",")","(","(",")","(","(","(",")","(","(","(",")","(",")","(","(","(",")","(",")",")","(",")","(",")","(",")",")",")",")",")",")","(",")",")",")","(",")",")","(","(","(","(","(","(",")",")","(",")","(","(","(",")","(",")",")","(",")","(","(","(","(","(",")","(","(","(","(","(","(",")","(","(","(",")",")","(",")","(",")","(",")","(",")",")","(",")","(","(","(",")",")","(","(","(",")",")",")","(",")","(","(","(",")",")","(","(",")","(",")",")",")","(","(",")","(",")","(",")","(",")",")",")","(","(","(",")","(","(","(","(",")","(",")","(","(","(",")","(",")",")","(","(","(",")","(",")",")",")",")",")","(",")",")",")","(","(",")","(",")",")",")",")","(","(","(",")",")","(",")","(",")","(",")","(",")","(",")",")",")",")",")","(","(",")","(",")","(",")","(","(",")",")",")","(","(","(","(","(","(","(",")","(","(",")",")","(",")",")","(",")","(",")","(",")",")",")",")",")",")",")","(",")",")","(","(","(","(","(",")",")",")","(","(","(","(","(",")","(",")",")","(","(",")",")","(",")","(","(",")","(","(",")",")","(","(","(",")",")",")","(",")","(",")","(",")","(","(","(","(","(","(",")",")","(","(","(","(",")",")",")","(",")",")","(","(","(","(",")",")","(","(",")",")","(",")","(",")","(",")","(",")","(",")",")",")","(","(","(","(","(","(",")","(","(",")","(","(","(","(","(",")",")","(","(","(","(",")","(",")",")","(",")","(","(",")","(",")","(",")","(","(",")","(",")","(","(","(",")",")",")","(","(",")","(",")","(",")",")","(","(",")",")","(","(","(",")",")","(","(",")",")",")",")","(","(",")","(",")",")","(","(",")",")","(","(",")","(","(",")",")",")",")",")",")","(","(",")","(",")","(",")",")",")",")","(","(",")",")","(","(",")",")","(",")",")",")","(","(","(","(","(",")",")","(",")","(",")",")","(",")","(","(",")","(","(","(",")",")",")",")","(",")",")",")",")",")",")","(","(","(","(",")","(","(","(","(",")","(","(","(","(","(",")","(",")",")","(","(",")","(","(","(","(","(","(","(",")","(","(","(",")",")",")",")","(","(","(","(","(","(","(",")",")","(",")",")","(","(","(","(",")",")",")","(",")","(",")",")",")","(","(","(","(","(","(",")","(",")",")",")","(","(",")","(",")",")",")",")","(","(","(","(",")",")",")",")","(","(",")",")",")","(","(",")","(",")",")",")",")",")",")",")","(",")","(",")","(","(",")",")","(","(",")","(","(",")","(","(","(","(","(",")",")",")",")","(",")",")","(",")","(","(",")",")",")",")",")","(","(",")","(",")",")","(","(","(",")",")",")","(","(","(","(",")","(","(","(","(",")","(",")","(",")",")","(",")",")",")","(",")",")","(",")",")",")",")",")",")",")",")",")",")",")","(",")","(","(","(","(","(",")","(",")","(","(","(","(",")","(","(",")",")",")",")",")",")",")",")","(","(","(","(","(","(",")","(",")","(",")","(",")","(",")",")",")",")",")","(",")","(",")",")","(",")",")",")","(","(",")",")",")","(","(","(",")","(",")","(","(",")",")","(","(","(",")","(","(",")","(","(","(","(","(","(",")","(","(","(",")","(","(",")","(",")","(","(","(","(",")",")",")","(",")","(",")",")","(","(",")",")",")","(","(","(",")","(",")","(",")","(","(","(","(",")","(","(","(","(",")",")","(",")","(","(",")","(","(","(",")","(","(",")","(",")","(","(",")","(","(",")",")",")",")",")",")","(","(","(",")","(","(",")",")",")","(",")","(","(","(","(",")",")","(","(",")",")","(",")",")",")","(",")",")","(",")",")",")","(","(","(","(","(","(","(","(",")","(","(","(",")",")",")",")",")","(",")",")",")","(",")",")",")","(",")","(","(",")","(","(",")",")",")","(","(","(",")",")",")","(","(",")",")","(",")",")","(",")",")","(","(","(",")","(",")",")",")","(","(",")",")","(",")",")",")",")","(",")",")","(",")","(","(",")","(","(",")",")",")",")","(","(","(","(","(","(",")","(","(","(","(","(",")",")",")",")",")","(",")",")","(",")","(",")",")",")",")",")",")",")","(",")","(",")","(",")",")","(",")","(",")","(",")",")","(",")",")","(",")","(","(","(","(","(","(",")","(","(",")",")","(","(",")","(",")","(","(",")","(","(","(","(","(","(",")",")",")",")",")",")","(","(","(","(",")",")","(",")",")","(",")","(","(",")",")","(","(",")","(",")","(",")",")",")","(",")","(","(",")","(","(",")",")",")","(","(","(",")","(","(","(","(",")",")","(","(","(",")","(",")","(",")",")","(","(",")","(",")","(","(","(","(","(","(","(",")",")",")",")","(","(",")",")",")",")","(","(",")",")",")",")","(",")","(",")","(","(","(","(",")",")",")","(",")",")","(",")",")","(","(",")","(","(",")","(","(",")",")","(",")",")",")","(",")","(","(",")",")",")","(",")",")",")",")",")",")","(","(",")",")",")",")","(","(","(",")",")","(",")",")","(",")",")",")","(","(","(","(","(","(",")","(","(",")","(",")",")",")","(","(","(","(","(",")",")",")","(",")","(","(",")",")",")",")",")","(","(","(",")",")",")",")",")",")","(","(",")","(",")","(",")","(",")",")","(",")",")",")",")",")",")","(",")",")","(","(","(","(",")","(","(","(","(","(","(",")","(","(",")","(",")",")",")",")",")","(",")","(",")",")","(",")","(","(",")","(",")","(",")","(",")","(",")","(","(","(",")",")",")",")","(",")",")","(",")","(",")",")",")",")",")","(",")",")",")",")","(","(","(","(",")","(",")",")","(","(","(","(","(","(","(",")","(","(","(","(",")",")","(",")",")","(","(","(","(",")","(",")","(","(","(","(",")",")","(","(","(",")",")","(","(","(","(",")","(","(","(","(","(",")",")","(","(","(",")","(","(",")","(",")","(","(","(","(","(",")","(",")",")","(","(","(","(","(","(",")",")",")","(","(",")","(",")",")","(","(","(",")","(",")","(",")","(",")","(",")","(",")","(","(",")",")","(","(","(",")","(","(","(",")",")","(",")","(","(","(",")",")","(","(","(",")","(",")","(",")","(",")","(",")","(","(",")",")",")",")","(","(","(",")","(",")","(","(","(","(",")","(","(",")",")",")",")","(","(","(","(",")","(",")",")","(","(",")","(","(",")",")",")",")",")",")",")",")","(","(","(",")",")",")",")",")","(",")","(",")",")",")",")","(","(",")",")",")",")",")",")","(",")",")","(","(",")","(","(",")",")",")",")",")",")",")",")","(",")","(","(",")","(","(",")",")","(",")","(",")",")","(","(","(","(",")",")",")","(","(",")","(","(",")","(","(",")","(","(",")",")",")","(","(",")","(",")","(","(","(","(",")",")",")","(","(",")","(","(","(",")","(",")","(","(","(",")","(",")","(",")",")",")","(",")",")",")",")","(","(","(","(","(","("];
father=[1,1,3,1,1,5,7,2,4,9,8,4,11,2,8,3,16,11,4,7,1,15,16,18,1,23,7,20,1,27,27,29,20,32,22,11,1,9,27,5,18,13,38,22,38,15,2,21,40,27,45,47,10,20,47,24,1,47,16,1,37,16,46,5,17,20,45,12,43,25,54,34,1,72,5,41,19,41,31,16,75,16,48,9,3,78,74,76,27,67,4,3,50,14,59,74,17,34,12,10,49,56,8,73,58,68,76,44,99,100,73,50,25,77,95,53,56,50,23,108,7,79,114,7,77,57,87,103,19,18,29,125,116,29,111,114,10,79,134,31,44,120,101,65,78,114,137,122,37,51,103,34,91,147,19,73,83,99,45,124,111,88,29,48,149,105,88,14,30,130,13,155,38,122,152,81,119,177,25,175,57,33,77,42,172,145,114,43,48,103,76,186,131,52,117,142,97,130,2,121,176,140,196,191,102,99,135,85,118,16,130,98,50,166,174,129,52,154,100,32,215,165,122,72,93,92,32,83,207,53,152,13,115,55,217,21,6,126,140,84,222,30,71,27,97,179,103,193,155,87,80,238,193,231,210,14,93,206,132,132,152,87,253,113,143,81,3,268,225,258,2,235,193,217,87,15,17,83,249,255,61,57,224,80,253,81,268,241,83,193,79,171,89,180,117,131,97,151,77,270,159,229,301,286,55,108,160,168,112,206,246,132,308,119,285,84,129,168,201,112,176,268,123,187,208,278,61,33,79,95,187,38,53,207,94,89,118,148,234,13,62,111,42,172,113,109,132,11,313,138,77,350,189,283,136,301,282,105,95,27,312,73,1,229,158,209,328,79,118,201,86,16,250,23,171,22,225,93,299,211,63,79,150,43,289,138,300,364,368,296,326,298,192,43,55,352,158,366,212,101,339,241,361,171,342,288,59,252,381,130,31,320,298,70,59,263,412,237,99,176,108,112,65,197,299,344,224,291,5,310,163,341,214,209,45,76,209,281,79,214,331,62,263,425,172,180,306,248,293,403,154,449,11,46,214,202,69,203,372,380,30,36,252,311,18,15,310,104,463,327,265,422,82,319,172,117,297,189,318,192,434,176,98,477,302,325,454,266,170,59,352,38,118,17,205,166,121,381,426,460,300,445,254,255,117,336,23,446,78,4,280,121,409,59,45,384,468,96,131,265,3,98,45,119,48,27,319,481,11,268,411,70,326,524,432,356,268,383,422,392,446,166,240,160,359,140,512,486,366,482,194,434,437,371,27,310,556,454,306,324,458,347,510,147,124,527,173,336,389,520,198,204,506,105,8,223,140,169,468,275,280,358,242,384,383,300,155,359,533,142,558,179,404,236,370,325,158,317,217,438,114,94,585,223,534,207,497,186,283,290,218,47,162,479,107,317,609,495,365,206,5,314,59,371,351,38,602,315,398,210,19,68,560,634,480,315,31,112,153,37,319,249,502,446,462,330,355,628,40,34,599,332,348,576,157,520,200,655,55,325,461,324,656,134,462,540,664,451,145,382,145,573,259,517,263,203,87,438,452,554,357,434,652,62,251,390,386,316,212,56,524,82,105,466,225,140,304,93,694,413,193,294,175,491,242,90,163,511,189,37,482,160,122,438,564,317,99,191,135,668,233,688,174,637,460,510,147,8,86,689,78,271,699,630,734,711,379,301,605,266,660,493,358,465,79,563,590,86,2,77,519,331,713,529,615,655,3,472,366,336,462,340,239,337,53,193,685,86,156,217,585,250,672,656,775,653,728,153,658,453,481,622,451,639,382,523,349,119,601,127,670,719,671,296,553,736,368,45,787,535,189,473,305,151,427,283,24,752,17,615,168,251,127,223,213,573,269,552,754,473,244,787,723,311,502,686,89,702,612,89,749,182,739,299,524,723,816,600,593,354,496,742,729,622,75,319,170,472,105,554,301,101,712,457,398,306,239,534,146,559,471,182,810,229,562,211,700,18,29,123,691,378,246,393,839,218,108,40,213,556,429,625,75,536,67,490,859,519,76,649,270,88,423,488,731,651,374,851,311,246,409,600,646,888,68,338,876,577,326,440,99,645,270,58,847,813,595,701,766,462,527,512,726,575,494,467,162,393,276,50,610,505,110,816,466,614,222,115,777,536,147,532,706,104,882,37,717,401,320,833,876,920,205,235,123,796,165,234,641,789,577,639,414,317,72,621,211,458,933,744,363,383,148,873,297,773,379,280,777,806,432,753,615,477,331,647,883,612,207,548,141,438,108,443,631,469,859,344,555,158,950,856,861,259,689,872,149,751,543,327,721,723,179,195,282,135,790,732,112,1017,732,550,801,771,882,346,545,95,1018,256,571,689,19,786,414,648,842,1031,339,216,679,704,955,556,831,524,848,716,284,1046,25,731,385,838,268,131,362,556,732,719,148,337,189,9,218,351,437,461,185,1057,124,223,782,1068,86,743,479,816,793,727,234,124,531,8,174,329,801,675,469,921,91,821,309,825,1011,775,899,386,593,567,619,689,692,494,440,514,52,1075,510,1025,140,254,56,890,875,227,972,510,197,70,687,30,963,8,75,547,21,123,784,207,740,926,896,1000,174,314,902,528,642,1012,1121,773,810,905,135,273,604,730,76,280,319,1086,307,1012,297,260,1125,749,1109,688,692,885,279,365,1069,546,179,913,504,776,1076,212,753,1142,19,583,134,671,723,929,636,972,606,374,938,663,424,127,239,621,7,719,867,35,115,145,11,935,455,981,777,1018,520,863,495,876,926,674,504,659,1134,432,22,1150,281,1123,282,255,747,699,78,433,244,90,984,714,116,1003,925,806,436,409,938,416,245,451,209,622,647,108,703,1017,857,61,820,692,552,287,652,537,363,479,351,1090,1231,200,1161,43,1133,33,1168,1144,369,294,1038,522,179,1122,453,1115,323,646,604,244,966,115,1179,740,730,1253,29,1250,88,1236,191,838,1262,604,1044,1008,583,1203,853,200,1202,620,685,259,590,1296,278,1174,199,71,832,709,796,419,624,128,716,701,1110,187,1018,906,1171,329,295,39,126,1269,1092,753,1322,14,1169,431,998,901,586,278,1029,160,13,26,1171,872,1096,20,376,1313,126,790,1202,363,528,641,1064,1047,124,789,14,1240,478,97,1056,313,419,569,66,1244,1363,1362,29,386,436,546,1273,937,1168,1158,405,547,595,1047,437,1333,490,32,769,1338,661,718,604,917,615,907,1006,183,448,214,290,1371,725,1050,897,748,390,793,1290,1235,697,136,686,732,518,1064,478,1203,345,1098,789,439,1104,622,1085,38,958,444,1175,461,591,1050,1229,671,288,97,1143,1203,1221,886,505,188,398,807,308,809,1028,948,972,143,632,1093,792,1320,1079,1033,1215,7,470,1083,548,1426,1299,164,364,883,1109,199,1009,812,865,1378,87,147,971,1277,362,662,892,38,831,392,284,16,1467,619,1157,1256,1145,216,699,1071,252,996,523,214,500,773,784,550,1317,48,635,1420,1182,573,662,1231,169,215,1351,317,236,90,1322,1194,1149,12,1162,1116,399,923,646,164,264,106,570,1103,1279,271,660,256,88,417,279,1120,610,1025,1435,353,1319,814,1179,1092,1304,701,1482,1141,827,785,955,231,263,482,438,194,368,1080,916,558,503,4,427,267,1328,144,1116,1523,866,468,751,736,818,565,470,27,752,913,134,1509,1080,1489,1392,54,1537,1500,1516,933,1537,473,797,1411,1278,1487,585,1551,705,775,1467,208,1411,1387,1116,1270,1031,949,784,157,834,149,1287,1466,1470,1067,1590,600,9,1159,522,371,122,848,43,1404,1569,18,827,910,1154,442,218,585,678,694,26,1004,1513,579,1388,1447,204,1431,203,907,696,474,930,1613,1529,877,1557,477,158,185,501,340,1484,88,1466,1607,460,385,207,144,51,1418,178,1580,231,97,1652,1635,989,1227,222,909,1538,898,939,1179,1428,769,1434,341,1380,1405,591,1261,1341,308,902,1025,900,820,1101,1596,1033,673,729,1658,618,122,644,707,366,881,1425,1601,1294,966,723,1001,4,220,1558,251,1329,225,456,1580,1369,1043,1130,245,1072,1319,103,1429,262,1,1513,733,285,1226,1698,114,1697,1358,1167,1150,690,317,1447,1350,763,955,1455,1134,1009,912,7,36,1625,1632,1214,789,1352,871,1309,1499,857,3,326,1131,796,792,719,702,1532,225,1607,1283,797,1162,1506,384,779,1571,396,1182,318,928,1295,1449,838,498,116,943,1457,616,1249,95,235,989,67,568,155,1000,1228,217,1010,187,975,225,813,633,1043,345,1097,1397,1637,10,544,78,890,982,1189,761,1147,298,26,1332,1292,1588,750,1560,816,127,1803,560,1017,199,31,540,1484,829,969,1483,1366,335,1216,66,1329,668,1524,930,1809,1839,980,1717,159,1783,1117,908,1609,1347,1481,1684,1819,934,779,1584,1240,1059,1714,1722,1229,1305,1432,129,1789,454,1110,594,392,734,1240,148,173,1250,488,1400,1329,640,161,245,936,1253,1602,1135,1348,1340,940,437,253,335,256,137,650,378,722,997,1554,1287,1892,1160,1563,225,473,292,550,1315,397,161,492,1409,1658,1191,1861,744,626,301,1536,920,1034,729,606,910,1426,847,638,953,1191,154,780,307,635,539,215,1794,894,382,1156,697,675,87,28,160,1812,459,403,1477,356,1507,1900,412,1630,1293,1867,1067,16,480,475,986,18,299,1230,1438,1959,1375,395,902,1437,1459,379,1259,1172,43,1531,347,1911,306,1578,990,1886,210,334,1574,700,736,1778,1855,617,1462,1399,69,562,343,116,53,1493,1044,1054,1485,270,564,721];